import java.sql.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class IntCmp implements Comparator<Integer> {
    public int compare(Integer o1, Integer o2) {
        return o1-o2;
  }
}
public class Heap {
   private int [] array;
    private int usedsize;

    public Heap() {
        this.array = new int[10];

    }
    //初始化数组的值，确定长度
    public void initHeap(int [ ]x) {
        for (int i = 0; i < x.length; i++) {
            array[i] = x[i];
            usedsize++;
        }
    }

    // 找倒数第一个非叶子节点，
    // 从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
    public void createHeap(){
        for (int praent = (usedsize-2)/2; praent >= 0 ; praent--) {
            shiftDown(praent,usedsize);

        }
    }

//向下调整
    private void shiftDown(int praent, int usedsize) {
        //左孩子的值
        int child =2*praent+1;
        while (child<usedsize) {
            if (child + 1<usedsize&&array[child] >  array[child + 1]) {
                child++;
            }
            if(array[child]<array[praent]){
                int tmp =array[praent];
                array[praent] = array[child];
                array[child] = tmp;
            }else {
                break;
            }
        }

    }

    //添加
    public void offer(int val){
        if(isFull()){
             this.array = Arrays.copyOf(array,2*array.length);
        }
        array[usedsize]=val;

        shifUp(usedsize);
        usedsize++;
    }
//先上调整
    private void shifUp(int usedsize) {
        int praent = (usedsize-1)/2;
        int child = usedsize;
       while (child>0) {
           if (array[child] < array[praent]) {
               int tmp = array[praent];
               array[praent] = array[child];
               array[child] = tmp;
               child = praent;
               praent = (praent - 1) / 2;

           } else {
             break;
           }
       }
    }

    //判断是否内存空间
    public boolean isFull(){
       return array.length == usedsize;
    }
    //删除
   public void Delete(int x){
       //根
        int praent = 0;
        //左孩子
        int child =2*praent+1;
     array[usedsize] =array[0];
     while (child<usedsize) {
         if (array[child] > array[child + 1]) {
             child++;
             array[praent] = array[child];
             praent = child;
             child = 2 * praent + 1;
         } else {
             array[praent] = array[child];
             praent = child;
             child = 2 * praent + 1;
         }
     }
     usedsize--;
   }
    //找出k个最小的数
    public int[] smallestK(int[] arr, int k) {
        if(arr == null||k<=0){
            return new int[0];
        }
        PriorityQueue <Integer> p = new PriorityQueue<>(arr.length);

        for(int i = 0;i<arr.length;i++){
             p.offer(arr[i]);
        }
        int []ret = new int [k];
        for (int i = 0; i < k; i++) {
            ret[i]=p.poll();
        }
     return ret;
    }


}


